1. Field of the Invention
The present invention is directed to communication networks and, more particularly, to routing and classifying messages in communication networks.
2. Background of the Related Art
Originally, the Internet was developed to support best effort services (such as data services) based on packet switched technologies while the telephony network provided circuit switched technologies to support dedicated connections such as for voice services. A network device 100 that can be employed in a network, such as the Internet, for switching packets is shown in FIG. 1.
Although best effort services were the original intent of packet-switched networks such as the Internet, there is a clear trend to support more improved and reliable services such as those supported by circuit-switched technologies. For example, a suite of Voice over Internet Protocol (VoIP) protocols and systems are under development and are being deployed. Furthermore, the Internet, which is based on IP protocols, will need to support a rich set of multimedia applications such as voice, data and video. To enable the Internet to transition from best effort service to a wide class of services, an emerging set of protocols such as differentiated services (diffserv) and integrated services (intserv) must be supported by switching elements throughout the network, such as network device 100.
These new protocols attempt to provide a means to distinguish one kind of packet (such as voice packets) from another kind of packet (such as best effort data packets) so that proper treatment is given to different kinds of packets. For example, in converged networks, premium treatment may be given to voice packets since voice packets have stringent delay and jitter requirements.
To distinguish between how different types of packets should be treated, packet classification is needed. Generally, packet classification can be characterized as matching a packet against a set of rules with multiple fields to identify the highest priority rule or rules matching the packet, and performing an action associated with the matching rule(s).
Packet classification plays an important role in many kinds of applications such as:                firewall or access control, network security, intrusion detection monitoring and signature matching;        policy based networking;        QoS queuing selection to meet service level agreement (SLA) and support differentiated services with QoS guarantee;        traffic accounting and billing, policing, and management; and        network address translation (NAT).        
For a firewall, static access control is currently one of the most popular applications for packet classification. An access control list (ACL) is maintained with sequential ordering. The first matching access control element is the rule to be applied to an incoming packet. The matching access control element is associated with an action (allow or deny the packet to go through). This is also called packet filtering. Typically a linear search is used for packet filtering. The static access control lists are generally configured by network operators and change less frequently while dynamic access control, which is also used in some firewall applications, may undergo frequent changes on the order of hundreds of changes per second.
Another popular application of packet classification noted above is policy based networking, which is used to enforce organizational policies such as automated operations, network management and control systems. In this context, a policy is a relationship between network objects such as particular groups of network elements, network resources/services, and user groups. For example, a company may enforce an authorization policy that gives the members in a particular department access to a particular service. Policy based networking relies on rules to automate network administration tasks such as configuration, performance, security, fault restoration, and service provisioning.
Differentiated services will be supported in the next generation networks. These require per-flow or per-class service queuing. So, packet classification is needed to identify which flow or class an incoming packet belongs to. It is critical to separate the packets from different flows or classes into different queues, which will be fairly dequeued by a packet scheduler, in order to meet service level agreements and guarantee QoS.
Billing is an important function of network equipment. Usage based billing has been used so that users are charged fairly based on the amount of their bandwidth usage. This requires classifying the packets in order to determine to which users they belong so as to perform traffic accounting and billing. Packet classification is also needed to police incoming traffic according to a service level agreement to prevent bandwidth stealing or detrimental usage, and to support denial of service (DoS) protection.
Finally, network address translation is used to conserve IP addresses since a shortage of IP addresses is becoming a problem due to the exponential growth of the Internet. NAT operates on a router between an intranet and public internet by translating between a special group of IP addresses, which are not Internet routable IP addresses defined by the Internet Assigned Numbers Authority (IANA) for use in private intranets, and public Internet routable IP addresses. For service providers, NAT saves the expense of registering large numbers of addresses with IANA. Enterprises can have their own internal IP address schemes and use only a limited number of IP addresses for public Internet access. NAT requires packet classification to perform one-to-one or many-to-one IP address translation by replacing the IP address in the IP header with a different IP address. The same applies to other fields such as the TCP/UDP port if port translation is desired.
FIG. 1 is a block diagram showing a conventional network device 100 that includes a switch engine 102 for determining how to treat different kinds of incoming packets in accordance with routing table 104. In an example where network device 100 is a typical present-day IP router, switch engine 102 determines how to forward packets to one or more of outputs 1 to N based solely on the IP destination address in the headers of the packets. In such an example, routing table 104 merely associates particular IP destination addresses with outputs 1 to N. However, next generation IP routers, in order to support the improved services mentioned above, may need to perform packet forwarding based on multiple fields in the packet headers. This means that conventional switch engine 102 and routing table 104 are inadequate for considering these different packet header fields in order to forward different types of packets in distinct ways. For example, voice packets may need to be forwarded to one output that is associated with a less congested path and has a quality of service (QoS) guarantee while data packets having the same IP destination address may need to be forwarded to an output associated with a different path that is more congested and has no QoS guarantee. Thus, traditional packet forwarding solely based on IP destination address is insufficient to handle this improved form of packet classification.
A simple packet classification algorithm is to compare an incoming packet against each classification rule sequentially. The complexities of this linear search is O(N) with O(N) memory, where N is the number of rules. The update can be made incrementally by using a binary search in the sorted list of rules in O(logN) time. Note that this algorithm needs the least amount of memory but its query time becomes unacceptable when the number of rules is large, which is the case in most practical applications. To speed up packet classification, more advanced data structures and algorithms should be used. Such advanced data structures will use more memory to store redundant information and thereby speed up packet classification. Clearly, there is a tradeoff between query time and memory size.
The prior art describes a scheme based on bit-parallelism to find the right tradeoff between query time and memory size. The characteristics in packet classifier rule databases (in particular for a firewall application) are taken advantage of in another prior art effort for multiple-stage packet classification. A heuristic approach is also considered in other efforts. Packet classification using tuple space search is given in additional efforts.
Primarily three approaches have been used for packet classification, namely, pure software, pure hardware, and a combination of software and hardware. In packet filtering or firewall applications, a pure software solution has been attempted. The main advantage of this approach is that software is flexible, easy to change and easy to upgrade. Its disadvantages are that software performs poorly, lacks efficiency, and is unable to scale to high-speed interfaces.
Due to high performance requirements and the complexity of the problem, hardware solutions such as a hard-wired ASICs have been pursued for packet classification. One hardware device called a ternary content addressable memory (TCAM), is a special type of fully associative memory where each cell has three logic states: 0, 1 and X (don't care). TCAMs allow a fully parallel search of the classifier database and are popularly used for packet classification. The disadvantages of a pure hardware solution are that hardware is inflexible, difficult to change to accommodate evolving network protocols, and has long development cycles. Furthermore, TCAMs have very high power consumption and support a fewer number of rules.
In next generation routers, a combination of the software and hardware approach is taken in a so-called “network processor”, which uses network application specific processors instead of a general-purpose processor. The advantages of this approach are that network processors are programmable, flexible, and can achieve performance comparable to a customized ASIC. This technique also shortens the time to market, can be easily changed or upgraded to accommodate new features or protocols, and adds product differentiation by customers. For example, the nP7120 Packet Processor from MMC Networks supports processing 13 million packets per second (MPPS) with dual 200 MHz processors optimized for packet processing. The IBM Rainier network processor uses 16 RISC cores for MAC & POS framing as well as packet classification with hundreds of rules at 1.6×OC48 speed. ClassiPI from PMC-Sierra uses two million logic gates (plus 2 MB RAM) for packet classification at OC48 speed.
Nevertheless, there remains a need for a high performance packet classification solution that provides an optimal tradeoff between performance and memory size.